1. Technical Field
The present invention relates to electronic design automation (EDA). More specifically, the present invention relates to a method and a system for performing routing on an integrated circuit (IC) using a dynamic grid.
2. Related Art
Advances in semiconductor technology presently make it possible to integrate large-scale systems, including hundreds of millions of transistors, onto a single semiconductor chip. This dramatic increase in semiconductor integration densities has made it considerably more challenging to efficiently perform routing in such a large-scale IC chip.
Routing an integrated circuit (IC) chip involves determining routes for metal wires which electrically connect integrated circuit devices to produce circuits that perform desired functions. Large scale IC chips are typically routed using routing software, which is typically referred to as a “routing system” or “router.”
Typically, a router searches for a route between pins/terminals using a graph-based approach. In the graph-based approach, the routing resources (i.e., path segments where wires can be routed) are usually represented as a regular three-dimensional (3D) grid. In the 3D grid, multiple metal layers can have different pitches. One technique to maintain regularity in the 3D grid requires making all pitches multiples of the smallest pitch. However, this technique can reduce useable tracks, and increase consumption of computational resources.
Furthermore, if a pin/terminal (hereinafter referred to as “pin”) is not located on a grid line, then wires cannot be routed to/from the pin. Conventional techniques add an off-grid track that passes through the pin's location to overcome this problem. Unfortunately, these techniques often propagate each off-grid track to all layers (one per each metal layer), which can be extremely wasteful in terms of memory usage and processing time.